package ecc;

/**
 * The EPoint class is an abstraction for the arithmetic in the group of
 * points on an elliptic curve over GF(p).<BR>
 * <BR>
 * A point of an elliptic curve is only meaningful when suitably attached
 * to some curve.  Hence, there must be no public means to create a point
 * by itself (i.e. concrete subclasses of EPoint shall have no public
 * constructor); the proper way to do this is to invoke the factory method
 * pointFactory() of the desired ECurve subclass.<BR>
 * <BR>
 * This is a direct application of the "Factory Method" design pattern
 * as described by E. Gamma, R. Helm, R. Johnson and J. Vlissides in
 * "Design Patterns - Elements of Reusable Object-Oriented Software",
 * Addison-Wesley (1995), pp. 107-116, especially Consequence #2
 * ("Connects parallel class hierarchies", pp. 109-110).<BR>
 * <BR>
 * This class must inherit from Cloneable to allow for the application of
 * the "Prototype" design pattern (see reference above) for uses of EPoint
 * where the actual nature of a curve point does not matter (e.g. in
 * general tests of implementation correctness).
 *
 * @author  Paulo S. L. M. Barreto
 */

import java.math.BigInteger;
import java.security.SecureRandom;

public class EPoint {

    private static final BigInteger
        _0 = BigInteger.valueOf(0L),
        _1 = BigInteger.valueOf(1L),
        _3 = BigInteger.valueOf(3L);

    public static final String differentCurves =
        "Cannot combine points from different elliptic curves";
    public static final String invalidCPSyntax =
        "Syntax error in curve point description";
    public static final String pointNotOnCurve =
        "The given point does not belong to the given elliptic curve";

    /**
     * The underlying elliptic curve, given by its parameters
     */
    public ECurve E;

    /**
     * Size of the underlying finite field GF(p)
     */
    public BigInteger p;

    /**
     * The projective x-coordinate
     */
    public BigInteger x;

    /**
     * The projective y-coordinate
     */
    public BigInteger y;

    /**
     * The projective z-coordinate
     */
    public BigInteger z;

    /**
     * Flag/mask for compressed, expanded, or hybrid point representation
     */
    public static final int
        COMPRESSED  = 2,
        EXPANDED    = 4,
        HYBRID      = COMPRESSED | EXPANDED;

    /**
     * Create an instance of the ECurve point at infinity on curve E.
     *
     * @param   E   the elliptic curve where the created point is located.
     */
    public EPoint(ECurve E) {
        this.E = E;
        p = E.p;
        /*
         * the point at infinity is represented as (1, 1, 0) after IEEE Std 1363:2000
         * (notice that this triple satisfies the projective curve equation y^2 = x^3 + a.x.z^4 + b.z^6)
         */
        x = _1;
        y = _1;
        z = _0;
    }

    /**
     * Create a normalized ECurve point from given affine coordinates and a curve
     *
     * @param   E   the underlying elliptic curve.
     * @param   x   the affine x-coordinate (mod p).
     * @param   y   the affine y-coordinate (mod p).
     */
    public EPoint(ECurve E, BigInteger x, BigInteger y) {
        this.E = E;
        this.p = E.p;
        this.x = x.mod(p);
        this.y = y.mod(p);
        this.z = _1; // normalized
        if (!E.contains(this)) {
            throw new IllegalArgumentException(pointNotOnCurve);
        }
    }

    /**
     * Create an ECurve point from a given affine x-coordinate, a y-bit and a curve
     *
     * @param   E       the underlying elliptic curve.
     * @param   x       the affine x-coordinate (mod p).
     * @param   yBit    the least significant bit of the y-coordinate.
     */
    public EPoint(ECurve E, BigInteger x, int yBit) {
        this.E = E;
        this.p = E.p;
        this.x = x.mod(p);
        if (this.x.signum() == 0) {
            this.y = E.sqrt(E.b); // square root always defined
        } else {
            BigInteger x2 = x.multiply(x).mod(p);
            BigInteger alpha = x2.add(E.a).multiply(x).add(E.b).mod(p); // alpha = x^3 + ax + b = (x^2 + a)x + b
            BigInteger beta = E.sqrt(alpha);
            if (beta == null) {
                throw new IllegalArgumentException(pointNotOnCurve);
            }
            this.y = (beta.testBit(0) == ((yBit & 1) == 1)) ? beta : beta.negate().mod(p);
        }
        this.z = _1; // normalized
        assert (!E.contains(this));
    }

    /**
     * Create an ECurve point from given projective coordinates and a curve.
     *
     * @param   E   the underlying elliptic curve.
     * @param   x   the affine x-coordinate (mod p).
     * @param   y   the affine y-coordinate (mod p).
     * @param   z   the affine z-coordinate (mod p).
     */
    private EPoint(ECurve E, BigInteger x, BigInteger y, BigInteger z) {
        this.E = E;
        this.p = E.p;
        this.x = x;
        this.y = y;
        this.z = z;
    }

    /**
     * Create a clone of a given point.
     *
     * @param   Q   the point to be cloned.
     */
    private EPoint(EPoint Q) {
        this.E = Q.E;
        this.p = E.p;
        this.x = Q.x;
        this.y = Q.y;
        this.z = Q.z;
    }

    /*
     * performing arithmetic operations on elliptic curve points
     * generally implies knowing the nature of these points (more precisely,
     * the nature of the finite field to which their coordinates belong),
     * hence they are done by the underlying elliptic curve.
     */

    /**
     * Check whether this is the point at infinity (i.e. the ECurve group zero element).
     *
     * @return  true if this is the point at infinity, otherwise false.
     */
    public boolean isZero() {
        return z.signum() == 0;
    }

    /**
     * Compare this point to a given object.
     *
     * @param   Q   the elliptic curve point to be compared to this.
     *
     * @return  true if this point and Q are equal, otherwise false.
     */
    public boolean equals(Object Q) {
        if (Q instanceof EPoint && this.isOnSameCurve((EPoint)Q)) {
            EPoint P = (EPoint)Q;
            if (z.signum() == 0 || P.isZero()) {
                return z.equals(P.z);
            } else {
                BigInteger
                    z2 = z.multiply(z ).mod(p),
                    z3 = z.multiply(z2).mod(p),
                    pz2 = P.z.multiply(P.z).mod(p),
                    pz3 = P.z.multiply(pz2).mod(p);
                return
                    x.multiply(pz2).subtract(P.x.multiply(z2)).mod(p).signum() == 0 &&
                    y.multiply(pz3).subtract(P.y.multiply(z3)).mod(p).signum() == 0;
            }
        } else {
            return false;
        }
    }

    /**
     * Check whether Q lays on the same curve as this point.
     *
     * @param   Q   an elliptic curve point.
     *
     * @return  true if Q lays on the same curve as this point, otherwise false.
     */
    public boolean isOnSameCurve(EPoint Q) {
        return E.p.equals(Q.E.p)
            && E.a.equals(Q.E.a)
            && E.b.equals(Q.E.b)
            && E.h.equals(Q.E.h)
            && E.n.equals(Q.E.n)
            // && E.G.equals(Q.E.G) // caveat: resist the temptation to uncomment this line! :-)
            ;
    }

    /**
     * Compute a random point on the same curve as this.
     *
     * @param    rand    a cryptographically strong pseudo-random number generator.
     *
     * @return  a random point on the same curve as this.
     */
    public EPoint randomize(SecureRandom rand) {
        return E.pointFactory(rand);
    }

    /**
     * Normalize this point.
     *
     * @return  a normalized point equivalent to this.
     */
    public EPoint normalize() {
        if (this.z.signum() != 0 && this.z.compareTo(_1) != 0) {
            assert (z.gcd(p).compareTo(_1) == 0);
            BigInteger zinv = z.modInverse(p);
            BigInteger zinv2 = zinv.multiply(zinv).mod(p);
            x = x.multiply(zinv2).mod(p);
            y = y.multiply(zinv2).multiply(zinv).mod(p);
            z = _1;
        }
        return this;
    }

    /**
     * Compute -this.
     *
     * @return  -this.
     */
    public EPoint negate() {
        return new EPoint(E, x, p.subtract(y), z);
    }

    /**
     * Compute this + Q.
     *
     * @return  this + Q.
     *
     * @param   Q   an elliptic curve point.
     */
    public EPoint add(EPoint Q) {
        /*
        if (!this.isOnSameCurve(Q)) {
            throw new IllegalArgumentException(differentCurves);
        }
        */
        if (this.isZero()) {
            return Q;
        }
        if (Q.isZero()) {
            return this;
        }
        // P1363 section A.10.5
        BigInteger t1, t2, t3, t4, t5, t6, t7, t8;
        t1 = x;
        t2 = y;
        t3 = z;
        t4 = Q.x;
        t5 = Q.y;
        t6 = Q.z;
        if (t6.compareTo(_1) != 0) {
            t7 = t6.multiply(t6); // t7 = z1^2
            // u0 = x0.z1^2
            t1 = t1.multiply(t7).mod(p);
            // s0 = y0.z1^3 = y0.z1^2.z1
            t2 = t2.multiply(t7).multiply(t6).mod(p);
        }
        if (t3.compareTo(_1) != 0) {
            t7 = t3.multiply(t3); // t7 = z0^2
            // u1 = x1.z0^2
            t4 = t4.multiply(t7).mod(p);
            // s1 = y1.z0^3 = y1.z0^2.z0
            t5 = t5.multiply(t7).multiply(t3).mod(p);
        }
        // W = u0 - u1
        t7 = t1.subtract(t4).mod(p);
        // R = s0 - s1
        t8 = t2.subtract(t5).mod(p);
        if (t7.signum() == 0) {
            return (t8.signum() == 0) ? Q.twice(1) : E.infinity;
        }
        // T = u0 + u1
        t1 = t1.add(t4).mod(p);
        // M = s0 + s1
        t2 = t2.add(t5).mod(p);
        // z2 = z0.z1.W
        if (!t6.equals(_1)) {
            t3 = t3.multiply(t6); // no need to reduce here
        }
        t3 = t3.multiply(t7).mod(p);
        // x2 = R^2 - T.W^2
        t5 = t7.multiply(t7).mod(p); // t5 = W^2
        t6 = t1.multiply(t5).mod(p); // t6 = T.W^2
        t1 = t8.multiply(t8).subtract(t6).mod(p);
        // 2.y2 = (T.W^2 - 2.x2).R - M.W^2.W
        t2 = t6.subtract(t1.shiftLeft(1)).multiply(t8).subtract(t2.multiply(t5).multiply(t7)).mod(p);
        t2 = (t2.testBit(0) ? t2.add(p) : t2).shiftRight(1).mod(p);
        return new EPoint(E, t1, t2, t3);
    }

    /**
     * Left-shift this point by a given distance n, i.e. compute (2^^n)*this.
     *
     * @param    n    the shift amount.
     *
     * @return (2^^n)*this.
     */
    public EPoint twice(int n) {
        // P1363 section A.10.4
        BigInteger t1, t2, t3, t4, t5;
        t1 = x;
        t2 = y;
        t3 = z;
        while (n-- > 0) {
            if (t2.signum() == 0 || t3.signum() == 0) {
                return E.infinity;
            }
            t4 = t3.multiply(t3); // t4 = z^2 (no need to reduce: z is often 1)
            if (E.a.add(_3).signum() == 0) { // a == -3
                // M = 3(x^2 - z^4) = 3(x - z^2)(x + z^2)
                t4 = _3.multiply(t1.subtract(t4).multiply(t1.add(t4))).mod(p);
            } else {
                // M = 3.x^2 + a.(z^2)^2
                t4 = _3.multiply(t1.multiply(t1)).add(E.a.multiply(t4).multiply(t4)).mod(p);
            }
            // z2 = 2.y.z
            t3 = t3.multiply(t2).shiftLeft(1).mod(p);
            // S = 4.x.y^2
            t2 = t2.multiply(t2).mod(p); // t2 = y^2
            t5 = t1.multiply(t2).shiftLeft(2).mod(p);
            // x2 = M^2 - 2.S
            t1 = t4.multiply(t4).subtract(t5.shiftLeft(1)).mod(p);
            // T = 8.(y^2)^2
            t2 = t2.multiply(t2).shiftLeft(3).mod(p);
            // y2 = M(S - x2) - T
            t2 = t4.multiply(t5.subtract(t1)).subtract(t2).mod(p);
        }
        return new EPoint(E, t1, t2, t3);
    }

    /**
     * Compute k*this
     *
     * @param   k   scalar by which the base point G is to be multiplied
     *
     * @return  k*this
     */
    public EPoint multiply(BigInteger k) {
        /*
         * This method implements the the quaternary window multiplication algorithm.
         *
         * Reference:
         *
         * Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone,
         *      "Handbook of Applied Cryptography", CRC Press (1997),
         *      section 14.6 (Exponentiation), algorithm 14.82
         */
        EPoint P = this.normalize();
        if (k.signum() < 0) {
            k = k.negate();
            P = P.negate();
        }
        byte[] e = k.toByteArray();
        EPoint[] mP = new EPoint[256];
        mP[0] = E.infinity;
        mP[1] = P;
        for (int m = 1; m <= 7; m++) {
            mP[2*m    ] = mP[  m].twice(1);
            mP[2*m + 1] = mP[2*m].add(P);
        }
        EPoint A = E.infinity;
        for (int i = 0; i < e.length; i++) {
            int u = e[i] & 0xff;
            A = A.twice(4).add(mP[u >>> 4]).twice(4).add(mP[u & 0xf]);
        }
        return A;
    }

    /**
     * Compute ks*this + kr*Y.  This is useful in the verification part of several signature algorithms,
     * and (hopely) faster than two scalar multiplications.
     *
     * @param   ks  scalar by which this point is to be multiplied.
     * @param   kr  scalar by which Y is to be multiplied.
     * @param   Y   a curve point.
     *
     * @return  ks*this + kr*Y
     */
    public EPoint simultaneous(BigInteger ks, BigInteger kr, EPoint Y) {
        assert (isOnSameCurve(Y));
        //return this.multiply(ks).add(Y.multiply(kr)).normalize();
        //*
        EPoint[] hV = new EPoint[16];
        hV[0] = E.infinity;
        hV[1] = this;
        hV[2] = Y;
        hV[3] = this.add(Y);
        for (int i = 4; i < 16; i += 4) {
            hV[i] = hV[i >> 2].twice(1);
            hV[i + 1] = hV[i].add(hV[1]);
            hV[i + 2] = hV[i].add(hV[2]);
            hV[i + 3] = hV[i].add(hV[3]);
        }
        int t = Math.max(kr.bitLength(), ks.bitLength());
        EPoint R = E.infinity;
        for (int i = (((t + 1) >> 1) << 1) - 1; i >= 0; i -= 2) {
            int m = (kr.testBit(i  ) ? 8 : 0) |
                    (ks.testBit(i  ) ? 4 : 0) |
                    (kr.testBit(i-1) ? 2 : 0) |
                    (ks.testBit(i-1) ? 1 : 0);
            R = R.twice(2).add(hV[m]);
        }
        return R.normalize();
        //*/
    }

    /**
     * Convert this curve point to a byte array.
     * This is the ANSI X9.62 Point-to-Octet-String Conversion primitive
     *
     * @param   formFlags   the desired form of the octet string representation
     *                      (EPoint.COMPRESSED, EPoint.EXPANDED, EPoint.HYBRID)
     *
     * @return  this point converted to a byte array using
     *          the algorithm defined in section 4.3.6 of ANSI X9.62
     */
    public byte[] toByteArray(int formFlags) {
        byte[] result;
        if (this.isZero()) {
            result = new byte[1];
            result[0] = (byte)0;
            return result;
        }
        normalize();
        byte[] osX = null, osY = null;
        osX = x.toByteArray();
        int pc = 0, resLen = 1 + osX.length;
        if ((formFlags & COMPRESSED) != 0) {
            pc |= COMPRESSED | (this.y.testBit(0) ? 1 : 0);
        }
        if ((formFlags & EXPANDED) != 0) {
            pc |= EXPANDED;
            osY = y.toByteArray();
            resLen += osY.length;
        }
        result = new byte[resLen];
        result[0] = (byte)pc;
        System.arraycopy(osX, 0, result, 1, osX.length);
        if (osY != null) {
            System.arraycopy(osY, 0, result, 1 + osX.length, osY.length);
        }
        return result;
    }

    public String toString() {
        normalize();
        return this.isZero() ? "O" : "(" + x + ", " + y + ")";
    }

	/**
	 * Verifies if the coordinates x, y and z of 
	 * this point match those of the point passed as parameter
	 * @param E
	 * @return
	 */
	public boolean equals(EPoint E){
		return (this.x.equals(E.x) && this.y.equals(E.y) && this.z.equals(E.z));
	}

}
